/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 //都是先访问中序，递归
class Solution {
public:
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

		if (preorder.empty())
		{
			return nullptr;
		}

		int leftpre = 0,rightpre = preorder.size();
		int leftin = 0, rightin = inorder.size() - 1;

		//先申请出根节点
		TreeNode* root = new TreeNode(preorder[0]);

		//分别存放左右子树
		vector<int> leftv;
		vector<int> rightv;

		//开始存放中序的右子树
		for (int i = 0; i < rightpre;i++)
		{
			if (inorder[i] != preorder[0])
			{
				rightv.push_back(inorder[i]);
			}
			else
			{
				break;
			}
		}
		int idx1 = 0,idx2 = 0;
		idx2 = rightv.size();

		//把左子树在放进去
		for (int i = 1; i <= idx2; i++)
		{
			leftv.push_back(preorder[i]);
		}
		idx1 = leftv.size();

		root->left = buildTree(leftv, rightv);

		//清空数据
		leftv.clear();
		rightv.clear();

		//右边的处理  
		//idx+1的原因是root值被取出了的
		for (int i = idx1 + 1; i < preorder.size();i++)
		{
			leftv.push_back(preorder[i]);
		}

		for (int i = idx2 + 1;  i < inorder.size();i++)
		{
			rightv.push_back(inorder[i]);
		}
		root->right = buildTree(leftv, rightv);


		return root;
	}

};